import java.util.Arrays;

public class Sort {
    public static void main(String[] args) {
        int[]array = {3,4,5,1,2};
        //selectSort(array);
        heapSort(array);
        System.out.println(Arrays.toString(array));
    }

    //选择排序
    public static void selectSort(int[] array) {

        for (int i=0; i < array.length-1; i++) {
           int minindex = i;
          for(int j= i+1;j< array.length;j++){
              if(array[j]<array[minindex]){
                  minindex = j;
              }
          }
            swap(array,minindex,i);
        }
    }
    //堆排序
    public static void heapSort(int[] array){
        createHeap(array);
        int end = array.length-1;
        while(end>0){
            swap(array,0, end);
            shiftDown(array,0,end);
            end--;
        }

    }

    private static void shiftDown(int[] array, int i, int end) {
        int child = i*2+1;
        while(child<end){
            if(child+1<end&&array[child+1]>array[child]){
                child++;
            }
            if(array[child]>array[i]){
                swap(array,i,child);
                 i =child;
                child = 2*i+1;
            }
            else break;
        }
    }

    private static void createHeap(int[] array) {
        int i = (array.length-2)/2;
        while(i>=0){
            shiftDown(array,i, array.length);
            i--;
        }
    }
    // 冒泡排序
    public static void bubbleSort(int[] array){
        // write code  here
    }

// 快速
    public static void quickSort(int[] array){
        // write code  here
    }

    private static void swap(int[]array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

}

